#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

import random


def reservoir(value_generator, k):
    reservoir = []
    for idx, value in enumerate(value_generator, 1):
        if idx <= k:
            reservoir.append(value)
        else:
            be_pick_prob = k/idx
            if random.random() > be_pick_prob:
                continue
            substitute_idx = random.randint(0, k-1)
            reservoir[substitute_idx] = value

    return reservoir


def main():
    print("start main")
    result = reservoir([1,2, 3], 3)
    print(sorted(result))

if __name__ == "__main__":
    main()
